package binarytree

// 递归
func findBottomLeftValue(root *TreeNode) int {
	maxDepth := 0
	maxDepthValue := 0

	var helper func(root *TreeNode, depth int)
	helper = func(root *TreeNode, depth int) {
		if depth > maxDepth && root.Left == nil && root.Right == nil {
			maxDepth = depth
			maxDepthValue = root.Val
		}
		if root.Left != nil {
			helper(root.Left, depth+1)
		}
		if root.Right != nil {
			helper(root.Right, depth+1)
		}
	}
	helper(root, 1)
	return maxDepthValue
}

// 迭代
func findBottomLeftValue2(root *TreeNode) int {
	queue := []*TreeNode{root}
	nodeList := []*TreeNode{root}
	for len(queue) > 0 {
		level := []*TreeNode{}
		length := len(queue)
		for i := 0; i < length; i++ {
			if queue[i].Left != nil {
				level = append(level, queue[i].Left)
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				level = append(level, queue[i].Right)
				queue = append(queue, queue[i].Right)
			}
		}
		queue = queue[length:]
		if len(level) > 0 {
			nodeList = level
		}
	}
	return nodeList[0].Val
}
